/**
 * Created by zhourh on 2018/9/26.
 *
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

 说明: 叶子节点是指没有子节点的节点。

 示例:
 给定如下二叉树，以及目标和 sum = 22，

 5
 / \
 4   8
 /   / \
 11  13  4
 /  \      \
 7    2      1
 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

 */
public class PathSum {

    public static void main(String[] args) {
        TreeNode root = Converter.convertArray2TreeNode(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1});
        System.out.println(new PathSum().hasPathSum2(root, 22));

        TreeNode root2 = Converter.convertArray2TreeNode(new Integer[]{1,2});
        System.out.println(new PathSum().hasPathSum2(root2, 1));

        TreeNode root3 = Converter.convertArray2TreeNode(new Integer[]{1});
        System.out.println(new PathSum().hasPathSum2(root3, 1));
    }

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null) {
            return root.val == sum;
        }

        boolean childHasPathSum = hasPathSum(root.left, sum) || hasPathSum(root.right, sum);

        if (childHasPathSum) {
            return true;
        }


        return dfsSum(root, sum, 0);

    }

    public boolean dfsSum(TreeNode node, int sum, int current) {
        if (node == null) {
            return false;
        }

        current += node.val;

        return current == sum || dfsSum(node.left, sum, current) || dfsSum(node.right, sum, current);

    }


    public boolean hasPathSum2(TreeNode root, int sum) {

        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null) {
            return root.val == sum;
        }

        return hasPathSum2(root.left, sum - root.val) || hasPathSum2(root.right, sum - root.val);

    }
}
